package org.example.Greedy_Algorithm;

public class Jumping_Game_II {
    public static void main(String[] args) {
        //跳跃游戏 II

        //给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
        //每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
        //0 <= j <= nums[i]
        //i + j < n
        //返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
        int[] nums = {7,0,9,6,9,6,1,7,9,0,1,2,9,0,3};
        int jump = jump(nums);
        System.out.println(jump);
    }

    //还是代码随想录牛逼，思路厉害，我还有待学习
    public static int jump(int[] nums) {
        if (nums.length==1) return 0;
        int step = 0;
        int maxstep;
        boolean flag = false;
        for (int i = 0; i < nums.length; i++) {
            maxstep = i + nums[i];
            if (maxstep >= nums.length - 1) {
                step++;
                break;
            } else {
                int temp = i + nums[i];
                int j;
                for (j = i + 1; j <= temp && j < nums.length - 1; j++) {
                    if (maxstep < j + nums[j]) {
                        maxstep = j + nums[j];
                        i = j-1;
                        flag = true;
                    }
                }
                if (!flag) {
                    i = i + nums[i];
                }
                step++;
                flag = false;
            }
        }
        return step;
    }

}
